package com.cet.qz.unit01.chapter1_1;

import edu.princeton.cs.algs4.In;

import java.time.LocalTime;
import java.util.Arrays;

/**
 * @program: algorithm
 * @description: 二分查找与暴力查找效率比较
 * @author: 陈恩涛
 * @create: 2021-01-08 22:08
 **/
public class Exec04 {

    public static int binarySearch(int[] a,int key,int lo,int hi){
        if(lo > hi)
            return -1;
        int mid = lo + (hi - lo) / 2;
        if(a[mid] == key)
            return mid;
        else if (a[mid] < key) {
            return binarySearch(a, key, mid + 1, hi);
        } else {
            return binarySearch(a,key,lo,mid-1);
        }
    }

    /*
     *方法描述： 二分查找
     *
     * @param a
     * @param key
     * @return int
     * @author chenentao
     * @date 2021/1/8 22:20
     */
    public static int binarySearch(int[] a,int key){
        return binarySearch(a,key,0,a.length-1);
    }

    /*
     *方法描述：暴力查找
     *
     * @param a
     * @param key
     * @return int
     * @author chenentao
     * @date 2021/1/9 11:56
     */
    public static int bruteForceSearch(int[] a,int key) {
        for (int i = 0; i < a.length; i++) {
            if(a[i] == key)
                return i;
        }
        return -1;
    }

    public static void main(String[] args) {

        In in1 = new In("src/com/cet/data/algs4-data/largeW.txt");
        //a数组长度为1000000
        int[] a = in1.readAllInts();
        In in2 = new In("src/com/cet/data/algs4-data/largeT.txt");
        //b数组长度为10000000
        int[] b = in2.readAllInts();

        //a,b数组无序，不能直接使用二分查找
        //双轴快排
        Arrays.sort(a);
        LocalTime now = LocalTime.now();
        long start = now.toNanoOfDay();
        int index = binarySearch(a, 917529);
        long end = LocalTime.now().toNanoOfDay();
        long seconds = end - start;
        if (seconds < 0) {
            seconds = LocalTime.MAX.toNanoOfDay() + seconds;
        }
        System.out.println("largeW中二分查找结果为"+index+",耗时为："+seconds/1e9+"秒");

        start = LocalTime.now().toNanoOfDay();
        index = bruteForceSearch(a, 917529);
        end = LocalTime.now().toNanoOfDay();
        seconds = end - start;
        if (seconds < 0) {
            seconds = LocalTime.MAX.toNanoOfDay() + seconds;
        }
        System.out.println("largeW中暴力查找结果为"+index+",耗时为："+seconds/1e9+"秒");
    }
}
